package LeetCode;

import java.util.Arrays;

/**
 * @author attcat
 * ---做一个有趣的程序员
 * @date 2022-10-05 16:56
 * @description 合并两个有序数组
 * 非递减顺序排列的整数数组nums1  nums2
 * 另外2个 m 和 n 分别表示nums1  nums2中的元素数目
 * 合并 nums1  nums2，使用合并后的数组按照 非递减顺序 排列
 * <p>
 * 输入 ：nums1=[1,2,3,0,0,0]
 * m=3
 * nums2=[2,5,6]
 * n=3
 * 输出 [1，2，2，3，5，6]
 */
public class LeetCode_88 {

    /****
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param
     * @return
     * 利用Arrays 输出
     */

    public int[] mergeByArrays(int[] nums1, int m, int[] nums2, int n) {

        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        //采用了快速排序的方法
        Arrays.sort(nums1);
        return nums1;
    }


    /***
     * 用数组，多空间复杂度
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     * @return
     */
    public int[] merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n;
        int[] temp = new int[k];
        for (int index = 0, nums1index = 0, nums2index = 0; index < k; index++) {

            if (nums1index >= m) {
                /****
                 * mun1 数组全部取完，全部取mun2 数组
                 *
                 * */
                temp[index] = nums2[nums2index];
                nums2index++;
            } else if (nums2index >= n) {
                /****
                 * mun2 数组全部取完，全部取mun1 数组
                 *
                 * */
                temp[index] = nums1[nums1index];
                nums1index++;
            } else if (nums1[nums1index] < nums2[nums2index]) {
                /***
                 * nums1数组元素，小于nums2数组元素  取mums 1数组
                 */
                temp[index] = nums1[nums1index];
                nums1index++;
            } else {
                /***
                 * nums2数组元素，小于nums1数组元素  取mums 2数组
                 */
                temp[index] = nums2[nums2index];
                nums2index++;
            }

        }
        return temp;


    }


    public int[] flashbackMerge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n;
        for (int index = k - 1, nums1index = m - 1, nums2index = n - 1; index >= 0; index--) {
            if (nums1index < 0) {
                /****
                 * mun1 数组全部取完，全部取mun2 数组
                 *
                 * */
                nums1[index] = nums2[nums2index];
                nums2index--;
            } else if (nums2index < 0) {
                /****
                 * mun2 数组全部取完，全部取mun1 数组
                 *
                 * */
                break;
            } else if(nums1[nums1index] > nums2[nums2index]){
                /***
                 * nums1数组元素，小于nums2数组元素  取mums 1数组
                 */
                nums1[index] =nums1[nums1index];
                nums1index--;
            }
            else {
                nums1[index] =nums2[nums2index];
                nums2index--;
            }
        }
        return nums1;

    }


    public static void main(String[] args) {
        int nums1[] = {1, 2, 3, 0, 0, 0};
        int m = 3;
        int nums2[] = {2, 5, 6};
        int n = 3;
        LeetCode_88 leetCode_88 = new LeetCode_88();
//        leetCode_88.mergeByArrays(nums1, m, nums2, n);
//        for (int i = 0; i < nums1.length; i++) {
//            System.out.println(nums1[i]);
//        }
        System.out.println("#########");

        int[] temp = leetCode_88.flashbackMerge(nums1, m, nums2, n);
        for (int i = 0; i < temp.length; i++) {
            System.out.println(temp[i]);
        }
    }

}
